<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二叉搜索树的封装</title>
    一、二叉搜索树的优势：<br>
        可以快速地找到关键字的数据项，并且可以快速地删除<br>
    二、二叉搜索树的缺陷：<br>
        1. 会出现非平衡树：<br>
        如果插入的数据是有序的数据，深度就会越来越深，结构就会像一个链表一样<br>
        2. 平衡二叉树插入/查找效率：O(logN)<br>
        3. 非平衡二叉树插入/查找效率：O(N)<br>
    三、保证树总是平衡的<br>
        只要大部分是平衡的，那时间复杂度也是接近O(logN)<br>
        1. AVL树 - 插入/删除操作相对于红黑树效率都不高<br>
        2. 红黑树<br>
    四、红黑树
</head>
<body>
    <script>
        class BinarySearchTree {
            constructor() {
                this.isRoot = null
            }            
            insert(key) {
                // 1. 根据key创建节点
                let newNode = new Node(key)
                if (this.root == null) { // 2. 判断根节点是否存在
                    // 3. 赋值根节点
                    this.root = newNode
                } else { // 存在根节点了
                    // 4. 先对根节点的左右子节点进行判断，向左或向右插入节点
                    insertNode(this.root, newNode)
                }
                function Node(key) {
                    this.key = key
                    this.left = null
                    this.right = null
                }
                function insertNode (node, newNode) {
                    if (newNode.key < node.key) { // 向左查找去插入
                        if (node.left == null) {
                            node.left = newNode
                        } else {
                            insertNode(node.left, newNode)
                        }
                    } else { // 向右查找去插入
                        if (node.right == null) {
                            node.right = newNode
                        } else {
                            insertNode(node.right, newNode)
                        }
                    }
                }
            }

            // 树的遍历：注意递归调用时，函数执行栈的应用 （还有一个层序遍历）
            // 1. 先序遍历
            preOrderTraversal(handler) {
                preOrderTraversalNode(this.root, handler)
                function preOrderTraversalNode(node, handler) {
                    if (node != null) {
                        // 1. 处理经过的节点
                        handler(node.key)

                        // 2. 处理经过节点的左子节点
                        preOrderTraversalNode(node.left, handler)

                        // 3. 处理经过节点的右子节点
                        preOrderTraversalNode(node.right, handler)
                    }
                }
            }
            
            // 2. 中序遍历
            midOrderTraversal(handler) {
                midOrderTraversalNode(this.root, handler)
                function midOrderTraversalNode(node, handler) {
                    if (node != null) {
                        // 1. 处理经过节点的左子节点
                        midOrderTraversalNode(node.left, handler)

                        // 2. 处理经过的节点
                        handler(node.key)

                        // 3. 处理经过节点的右子节点
                        midOrderTraversalNode(node.right, handler)
                    }
                }
            }
            
            // 3. 后序遍历
            backOrderTraversal(handler) {
                backOrderTraversalNode(this.root, handler)
                function backOrderTraversalNode(node, handler) {
                    if (node != null) {
                        // 1. 处理经过节点的左子节点
                        backOrderTraversalNode(node.left, handler)

                        // 2. 处理经过节点的右子节点
                        backOrderTraversalNode(node.right, handler)

                        // 3. 处理经过的节点
                        handler(node.key)
                    }
                }
            }
            
            // 4. 最大值
            max() {
                if (!this.root) return null
                let node = this.root
                while(node.right) {
                    node = node.right
                }
                return node.key
            }
            
            // 5. 最小值
            min() {
                if (!this.root) return null
                let node = this.root
                while(node.left) {
                    node = node.left
                }
                return node.key
            }
            
            // 6. 搜索特定key
            search(key) {
                if (!this.root) return false
                let node = this.root
                while(node) {
                    if (key > node.key) {
                        node = node.right
                    } else if(key < node.key) {
                        node = node.left
                    } else {
                        return true
                    }
                }
                return false
            }

            // 7. 删除节点
            // 1. 先找到要删除的节点，如果没有找到，不需要删除
            // 2. 找到要删除的节点
            //     2.1 删除叶子节点
            //     2.2 删除只有一个子节点的节点
            //     2.3 删除有两个子节点的节点
            remove(key) {
                // 1. 寻找要删除的节点
                let current = this.root
                let parent = null // 通过父节点来管理删除和节点更新
                let isLeftChild = true // 判断要删除的节点是左还是右子节点
                
                // 开始寻找要删除的节点
                while(current.key != key) {
                    parent = current
                    if (key < current.key) {
                        isLeftChild = true
                        current = current.left
                    } else {
                        isLeftChild = false
                        current = current.right
                    }
                    // 找到叶子节点，还没有找到key
                    if (current == null) {
                        return false // 没有节点，删除失败
                    }
                }
                // 2. 根据对应的节点的情况删除节点
                // 此时找到了current.key == key

                // 2.1 删除的节点是叶子节点
                if (current.left == null && current.right == null) {
                    if (current == this.root) {
                        this.root = null
                    } else if (isLeftChild) {
                        parent.left = null
                    } else {
                        parent.right = null
                    }
                }
                
                // 2.2 删除的节点有一个子节点
                else if (current.right == null) {
                    if (current == this.root) {
                        this.root = current.left
                    } else if (isLeftChild) {
                        parent.left = current.left
                    } else {
                        parent.left= current.right
                    }
                } else if (current.left == null) {
                    if (current == this.root) {
                        this.root = current.right
                    } else if (isLeftChild) {
                        parent.right = current.left
                    } else {
                        parent.right = current.right
                    }
                }
                
                // 2.3 删除的节点有两个子节点
                else {
                    let successor = getSuccessor(current)
                    if (current == this.root) {
                        this.root = successor
                    } else if (isLeftChild) {
                        parent.left = successor
                    } else {
                        parent.right = successor
                    }
                    successor.left = current.left
                }
                // 规律：右节点里面的左叶子节点去替换不会影响二叉树结构
                // 步骤：
                    // 1. 找到要删除节点的右节点里面的左叶子节点
                    // 2. 如果没有，则直接使用要删除节点的右节点（叶子节点）
                    // 3. 将叶子节点替换要删除节点的父节点的左节点或右节点
                    // 4. 将要删除节点的右节点做为找到的叶子节点的右子节点

                function getSuccessor(delNode) {
                    // 1. 定义变量，保存找到的后继
                    let successor = delNode
                    let current = delNode.right
                    let successorParent = delNode

                    // 2. 循环查找
                    while (current != null) {
                        successorParent = successor
                        successor = current
                        current = current.left
                    }
                    
                    // 3. 判断寻找的后继节点是否直接就是delNode的right节点
                    if (successor != delNode.right) {
                        successorParent.left = successor.right
                        successor.right = delNode.right
                    }
                    return successor
                }
            }
        }

        // 调试代码
        // 1. 创建BST
        let bst = new BinarySearchTree()

        // 2. 插入数据
        bst.insert(11)
        bst.insert(7)
        bst.insert(15)
        bst.insert(5)
        bst.insert(3)
        bst.insert(9)
        bst.insert(8)
        bst.insert(10)
        bst.insert(13)
        bst.insert(12)
        bst.insert(14)
        bst.insert(20)
        bst.insert(18)
        bst.insert(25)
        bst.insert(6)
        console.log(bst)

        // 3. 测试遍历
        let resultString = ''
        bst.preOrderTraversal(function (key) {
            resultString += key+' '
        })
        console.log(`1. 先序遍历：${resultString}`)
        resultString = ''
        bst.midOrderTraversal(function (key) {
            resultString += key+' '
        })
        console.log(`2. 中序遍历：${resultString}`)
        resultString = ''
        bst.backOrderTraversal(function (key) {
            resultString += key+' '
        })
        console.log(`3. 后序遍历：${resultString}`)

        // 4. 最大值
        console.log(`最大值：${bst.max()}`)

        // 5. 最小值
        console.log(`最小值：${bst.min()}`)

        // 6. 搜索特定的值
        console.log(`搜索key值为11是否存在：${bst.search(11)}`)
        console.log(`搜索key值为8是否存在：${bst.search(8)}`)
        console.log(`搜索key值为6是否存在：${bst.search(6)}`)
        console.log(`搜索key值为20是否存在：${bst.search(20)}`)
        console.log(`搜索key值为19是否存在：${bst.search(19)}`)

        // 7. 删除节点
        bst.remove(15)
        console.log(bst)
        bst.remove(11)
        console.log(bst)
    </script>
</body>
</html>